/**
 * Created by IntelliJ IDEA.
 * User: Alexander Fedulin
 * Date: 07.12.11
 * Time: 12:10
 * To change this template use File | Settings | File Templates.
 */

import java.io.*;
import java.util.*;
import java.util.concurrent.TimeUnit;

public class Gift {

    private String problem_input = "gift.in";
    private String problem_output = "gift.out";
    private BufferedReader br;
    private StringTokenizer st;
    private PrintWriter out;

    String nextToken() throws IOException {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    int D, n, m;
    int a[][] = new int[100][100];
    int c[][] = new int[100][100];
    int dp[][] = new int[100][101];
    int usd = 0;
    int inf = 30000;


    void load() throws IOException {
        D = nextInt();
        n = nextInt();
        m = nextInt();
        for (int i = 0; i < m; i++)
        	for (int j = 0; j < n; j++)
                a[i][j] = nextInt();
        for (int i = 0; i < m; i++)
        	for (int j = 0; j < m; j++)
                	c[i][j] = nextInt();
        inf = D + 1;
        for (int i = 0; i < m; i++)
            for (int j = 0; j <= n; j++)
                dp[i][j] = -1;
    }

    int f(int i, int j)
    {
        if (j == n) return 0;
        if (dp[i][j] != -1) return dp[i][j];
        dp[i][j] = inf;
        for (int k = 0; k < m; k++)
            dp[i][j] = Math.min(dp[i][j], f(k, j + 1) + a[k][j] + c[i][k]);
        return dp[i][j];
    }

    void solve()
    {
    	usd++;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < m; j++)
                for (int k = 0; k < m; k++)
                    c[j][k] = Math.min(c[j][k], c[j][i] + c[i][k]);
        int res = inf;
        for (int i = 0; i < m; i++)
        {                	
            res = Math.min(res, f(i, 0));
        }
        if (res <= D)
            out.println(D - res);
        else out.println(-1);
    }
                           
    /*
    int d[] = new int[101 * 101 + 10];
    TreeSet <Integer> was;

    void solve()
    {
        was.clear();
        for (int i = 0; i < m; i++)
        {
            d[i * (n + 1)] = 0;
            was.add(i * (n + 1));
        }
        int res = inf;
        while (was.size() > 0)
        {
            int ver = was.pollFirst();
            if (ver % (n + 1) == n)
            {
                res = Math.min(d[ver], res);
            }
            if (d[ver] >= inf) break;
            int x = ver / (n + 1);
            int y = ver % (n + 1);
          //  System.err.println(x + " " + y + " : " + d[ver]);
            if (y < n && d[ver + 1] > d[ver] + a[x][y])
            {
                if (was.contains(ver + 1))
                    was.remove(ver + 1);
                d[ver + 1] = d[ver] + a[x][y];
                was.add(ver + 1);
            }
            for (int k = 0; k < m; k++)
            {
                    if (d[k * (n + 1) + y] > d[ver] + c[x][k])
                    {
                        if (was.contains(k * (n + 1) + y))
                            was.remove(k * (n + 1) + y);
                        d[k * (n + 1) + y] = d[ver] + c[x][k];
                        was.add(k * (n + 1) + y);
                    }
            }
        }

        if (res <= D)
            out.println(D - res);
        else out.println(-1);
    }
    */

    void run() {
        try {
            boolean online_judge = System.getProperty("ONLINE_JUDGE") != null;
            if (online_judge) {
                br = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(new OutputStreamWriter(System.out));
            } else {
                br = new BufferedReader(new FileReader(problem_input));
                out = new PrintWriter(new FileWriter(problem_output));
            }
            /*was = new TreeSet<Integer>(new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                if (d[o1] != d[o2])
                    return d[o1] - d[o2];
                return o1 - o2;
            }
            });
            */
		//	Arrays.fill(was, 0);
			//System.err.println("ok\n");
            int T = nextInt();
            for (int i = 0; i < T; i++)
            {
                load();
                solve();
            }
            out.close();

        } catch (Exception e) {
            e.printStackTrace();
            System.exit(42);
        }
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    public static void main(String args[]) {
        long start = System.currentTimeMillis();
        new Gift().run();
        long finish = System.currentTimeMillis();
        System.err.println(finish - start + " ms");
    }
}
